package tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目： 按之字形顺序打印二叉树
 * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
 * 第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
 * @Author Gavin
 * @date 2022.08.06 21:48
 */
public class tree_22 {
    /**
     * 解题思路：
     *  利用一个队列逐层打印，然后利用一个变量控制每层是否翻转就行了
     */
    public ArrayList<ArrayList<Integer>> solution(TreeNode root){
        if(root==null)return null;
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean flag=true;
        while (!queue.isEmpty()){
            int c=queue.size();
            ArrayList<Integer> preResult=new ArrayList<>();
            while (c-->0){
                TreeNode pre=queue.poll();
                if(pre==null)continue;
                preResult.add(pre.val);
                queue.add(pre.left);
                queue.add(pre.right);
            }
            flag=!flag;
            if(flag){
                Collections.reverse(preResult);
            }
            if(preResult.size()>0){
                result.add(preResult);
            }
        }
        return result;
    }
}
